# # 快排 时间复杂度 O(nlogn)
#
# def partition(li, left, right):
#     tmp = li[left]
#     while left < right:
#         while left < right and li[right] >= tmp:  # 从右面找比tmp小的数
#             right -= 1  # 往左走一步
#         li[left] = li[right]  # 把右边的值放在左边空位上
#         while left < right and li[left] <= tmp:  # 从左面找比tmp的数
#             left += 1  # 往右走一步
#         li[right] = li[left]  # 把左边的值放在右边空位上
#     li[left] = tmp  # 把tmp归位到中间
#     return left
#
#
# def quick_sort(li, left, right):
#     if left < right:
#         mid = partition(li, left, right)
#         quick_sort(li, left, mid - 1)
#         quick_sort(li, mid + 1, right)
#
#
# li = [5, 7, 4, 6, 3, 1, 2, 9, 8]
# print(li)
# quick_sort(li, 0, len(li) - 1)
# print(li)
import random


def s(a, l, r):
    i = l
    j = r
    mid = a[l]
    while i < j:
        while i < j and a[j] > mid:
            j -= 1
        while i < j and a[i] <= mid:
            i += 1
        if i < j:
            a[i], a[j] = a[j], a[i]
    a[l], a[i] = a[i], a[l]
    return i

def dg(a, l, r):
    if l < r:
        mid = s(a, l, r)
        dg(a, l, mid-1)
        dg(a, mid+1, r)


a = [random.randint(1, 100) for i in range(20)]
print(a)
dg(a, 0, len(a)-1)
print(a)
